class Solution {
    bool row[9][10];
    bool col[9][10];
    bool grid[3][3][10];
 
public:
    void solveSudoku(vector<vector<char>>& board) {
        for(int i = 0; i < 9; ++i) // 初始化
        {
            for(int j = 0; j < 9; ++j)
            {
                if(board[i][j] != '.')
                {
                    int n = board[i][j] - '0';
                    row[i][n] = col[j][n] = grid[i / 3][j / 3][n] = true;
                }
            }
        }
        dfs(board);
    }
 
    bool dfs(vector<vector<char>>& board)
    {
        for(int i = 0; i < 9; ++i)
        {
            for(int j = 0; j < 9; ++j)
            {
                if(board[i][j] == '.')
                {
                    for(int n = 1; n <= 9; ++n)
                    {
                        if(!row[i][n] && !col[j][n] && !grid[i / 3][j / 3][n])
                        {
                            board[i][j] = n + '0'; // 填数
                            row[i][n] = col[j][n] = grid[i / 3][j / 3][n] = true;
                            if(dfs(board) == true) // 填对了，告诉上一层填对了
                                return true;
                            board[i][j] = '.'; // 回复现场
                            row[i][n] = col[j][n] = grid[i / 3][j / 3][n] = false;
                        }
                    }
                    return false; // 1到9都不行
                }
            }
        }
        return true; // 填完了
    }
};